package E_2024;
/*
    如果3个正整数(a,b,c)满足a2 + b2 = c2的关系，则称(a,b,c)为勾股数（著名的勾三股四弦五），
    为了探索勾股数的规律，我们定义如果勾股数(a,b,c)之间两两互质（即a与b，a与c，b与c之间均互质，没有公约数），则其为勾股数元组（例如(3,4,5)是勾股数元组，(6,8,10)则不是勾股数元组）。
    请求出给定范围[N,M]内，所有的勾股数元组。
输入描述
    起始范围N，1 <= N <= 10000
    结束范围M，N < M <= 10000
输出描述
    1. a,b,c请保证a < b < c,输出格式：a b c；
    2. 多组勾股数元组请按照a升序，b升序，最后c升序的方式排序输出；
    3. 给定范围中如果找不到勾股数元组时，输出”NA“。
    示例1 输入输出示例仅供调试，后台判题数据一般不包含示例
 输入
     1
     20
输出
    3 4 5
    5 12 13
    8 15 17
 */
/*
0001
0010
0011
0100
0101
0110
0111
1000
1001
1010
 */
public class E_100_47 {
    public static void main(String[] args) {
        ans(1,10000);
    }
    // 主要有两点
    // 1. 如何判断勾股
    // 2. 如何判断公约数
    public static void ans(int n, int m){
        StringBuilder sb = new StringBuilder();
        for (int i = n; i <= m; i++) {
            for (int j = i+1; j <= m; j++) {
                int sqrt = sqrt(i * i + j * j);
                if (sqrt == -1) continue;
                if (kf(i,j) && kf(j,sqrt) && kf(i,sqrt))
                    sb.append(i).append(' ').append(j).append(' ').append(sqrt).append('\n');
            }
        }
        if (sb.length() == 0) sb.append("NA");
        System.out.println(sb.toString());
    }
    // 开方与平方后值相同
    public static int sqrt(int num){
        double sqrt = Math.sqrt(num);
        int x = (int)sqrt;
        return x*x == num ? x : -1;
    }
    // 大数对小数循环做余，直到小数为0，判断大数是否为1
    public static boolean kf(int x, int y){
        while(x > 0){
            int mid = y % x;
            y = x;
            x = mid;
        }
        return y == 1;
    }
}
